package exampleQuestions;

import java.util.Arrays;

public class FindMaxSubSet {

	/**
	 * There is an Array with positive and negative integers randomly
	 * distributed. find the maximum sum of a subset of this array. (subset
	 * could contain any number of elements but not the adjacent elements).
	 * Follow up, what is the complexity of your algo. You can use additional
	 * Datastructures if you want.
	 */
	public static void main(String[] args) {

		int[][] array = { { 7, 11, 5 }, { 5, 2, 12 }, { 10, 0, 14 },
				{ 0, 0, 0 }, { 5, 0, 1 }, { 0, 0, 0 }, { 21, 3, 5 },
				{ 5, 7, 0 } };
		
		int []array2 = {5, 7, 10, 11, -5, 4, 0, -20, 15, 1};

//		System.out.println(getMaxSum(array));
		System.out.println(getMaxSum2(array2));
		
	}

	private static int getMaxSum2(int[] array2) {
		
		if (array2 == null || array2.length == 0) {
			return 0;
		} else {
			int []sum = new int[array2.length];
			sum[0] = array2[0] > 0 ? array2[0] : 0;
			for (int i=1; i<array2.length; i++) {
				sum[i] = Math.max(getMax2(i-1, sum), getMax2(i-2, sum) + array2[i]);
			}
			
			return sum[array2.length -1];
		}
	}

	private static int getMax2(int i, int[] sum) {
		return i>=0 ? sum[i] : 0;
	}

	private static int getMaxSum(int[][] array) {

		int sum[][] = new int[array.length][array[0].length];

		for (int j = 0; j < sum[0].length; j++) {
			for (int i = 0; i < sum.length; i++) {
				sum[i][j] = getMax(i, j, sum, array);
			}
		}
		
		System.out.println(Arrays.toString(sum[7]));

		return sum[array.length - 1][array[0].length - 1];
	}

	private static int getMax(int i, int j, int[][] sum, int[][] array) {
		
		return Math.max(getValue(i-1, j-1, sum), Math.max(getValue(i-1, j, sum), Math.max(getValue(i, j-1, sum), Math.max(getValue(i-2, j, sum)+array[i][j], getValue(i, j-2, sum)+array[i][j]))));
	}

	private static int getValue(int i, int j, int[][] sum) {
		return (i>=0 && j>=0) ? sum[i][j] : 0;
	}
	

}
